package cn.dapeng.math;


/**
 * 神奇数字
 * 给定三个数字， a, b, n，三个数字都不为负数
 * <p>
 * 如果某个数字既能整除a，又能整除b，那么称这个数字为神奇数字
 * <p>
 * 求第n个神奇数字是什么?
 * <p>
 * <p>
 * 解题思路：
 * 1. 首先可以确定这个神奇数字的最大范围是Math.min(a,b) * n
 * 2. 因为存在那个最大的数字，所以这个神奇数字肯定在最大范围以内。
 * 3. 借用二分法策略寻找这个第n个神奇数字的位置
 * <p>
 * 测试链接 : https://leetcode.cn/problems/nth-magical-number/
 */
public class NthMagicalNumber {


    public static int nthMagicalNumber(int a, int b, int n) {
        long lcm = MathUtil.lcm(a, b), ans = 0;

        // 使用二分法处理第N个神奇数字
        // l 等于 0 左边界 r 等于右边界 m 等于中间值
        for (long l = 0, r = (long) Math.min(a, b) * n, m = 0; l <= r; ) {
            m = (l + r) / 2;
            // 计算 0 ~ m 内出现的神奇数字个数 m / a + m / b - m / a和b的最小公倍数
            if (m / a + m / b - m / lcm >= n) {
                ans = m;
                r = m - 1;
            } else {
                l = m + 1;
            }
        }
        return (int) (ans % 1000000007);
    }

    public static void main(String[] args) {
        System.out.println(nthMagicalNumber(40000, 40000, 1000000000));
    }
}
